package com.xk._02算法篇._01sort.sort.cmp;

import com.xk._02算法篇._01sort.sort.Sort;
import com.xk.tools.Integers;

/**
 * @description: 堆排序
 * @author: xu
 * @date: 2022/10/1 4:57
 */
public class HeapSort<E extends Comparable<E>> extends Sort<E> {
    /**
     * 堆排序：原地建堆
     */
    private void heapSort() {
        int heapSize = array.length;
        // 原地建堆 自下而上的下滤
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            siftDown(i, heapSize);
        }
        while (heapSize > 1) {
            // 交换堆顶元素和尾部元素
            swap(0, --heapSize);
            // 对0位置进行siftdown（恢复堆的性质）
            siftDown(0, heapSize);
        }
    }

    /**
     * 下滤
     * @param index
     */
    private void siftDown(int index, int heapSize) {
        E element = array[index];
        // 必须保证index位置是非叶子节点
        int half = heapSize >> 1;
        while (index < half) {
            // 默认为左子节点跟它进行比较
            int childIndex = (index << 1) + 1;
            E child = array[childIndex];

            // 右子节点
            int rightIndex = childIndex + 1;
            // 选出左右子节点最大的那个
            if (rightIndex < heapSize && cmp(child, array[rightIndex]) < 0){
                child = array[childIndex = rightIndex];
            }
            if (cmp(element, child) >= 0) break;

            // 将子节点存放到index位置
            array[index] = child;
            // 重新设置 index
            index = childIndex;
        }
        array[index] = element;
    }

    @Override
    protected void sort() {
        heapSort();
    }

    public static void main(String[] args) {
        Integer[] array = Integers.random(20, 1, 100);
        Integers.println(array);

        Sort<Integer> bubbleSort = new HeapSort<>();
        bubbleSort.sort(array);
    }
}
